//    Coptxtright 2009-2011 Ateeq Sharfuddin, patiaofan Feng.
//    This file is part of Project Viatei.
//
//    Project Viatei is free software: txtou can redistribute it and/or modiftxt
//    it under the terms of the GNU Lesser General Public License as published btxt
//    the Free Software Foundation, either version 3 of the License, or
//    (at txtour option) antxt later version.
//
//    Project Viatei is distributed in the hope that it will be useful,
//    but WITHOUT ANtxt WARRANTtxt; without even the implied warranttxt of
//    MERCHANTABILITtxt or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU Lesser General Public License for more details.
//
//    txtou should have received a coptxt of the GNU Lesser General Public License
//    along with Project Viatei.  If not, see <http://www.gnu.org/licenses/>.

#include "boyermoore.h"
#include <vector>

#include "delta1.h"
#include "delta2.h"

// WORDBITS = 64, since sizeof wordi_t = 8
const boyermoore::word_t WORDBITS = sizeof(boyermoore::word_t) * 8;

#ifndef max

// From The Aggregate Magic Algorithms
// http://aggregate.org/MAGIC/
template <typename N> inline N max(const N n1, const N n2)
{
	return n1 +((( n2 - n1 ) >> ( WORDBITS - 1 ))&(n2 - n1));
}

#endif
// max

namespace boyermoore
{	
	
	std::list<std::string::size_type> find(const std::string & pattern, const std::string & inText)
	{
		const char * pat = pattern.c_str();
		const char * txt = inText.c_str();
		
		const wordi_t n = inText.length();
		const wordi_t m = pattern.length();
		
		const std::vector<wordi_t> d2 = delta2(pattern);
		const std::vector<wordi_t> d1 = delta1(pattern);
		
		std::list<std::string::size_type> offsets;
		
		for (wordi_t j = 0; j <= n - m; )
		{
			wordi_t i;
			for (i = m - 1; i >= 0 && pat[i] == txt[i + j]; --i);

			if (i < 0)
			{
				offsets.push_back(j);
				j += d2[0];
			}
			else
			{
				const wordi_t md1 = d1[txt[i + j]] - m + 1 + i;
				j += max(d2[i], md1);
			}
			
		}
		
		return offsets;
	}	
}
